package com.zjj.algorithm.learning.atguigu.sort;

import java.util.Arrays;

/**
 * 基数排序
 * 思想：
 * 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
 * 然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
 * <p>
 * 使用基数排序，排 80000 个数据，用时 10 ~ 30 ms
 * 当数组个数比较大时就出出现 OOM，Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
 *
 * @author zjj_admin
 * @date 2022/11/19 21:48
 */
public class RadixSort {

    public static void main(String[] args) {

//        int[] arr = new int[]{53, 3, 542, 748, 14, 214};
////        int[] arr = new int[]{1, 10, 125};
//        radixSort(arr);

        //测试排 80000 个数据用时
        int[] arr = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
        long time1 = System.currentTimeMillis();

        radixSort(arr);
        long time2 = System.currentTimeMillis();
//        System.out.println("arr = " + Arrays.toString(arr));
        System.out.printf("使用基数排序，排 %d 个数据，用时 %s ms", arr.length, (time2 - time1));

    }


    /**
     * 当使用了 getBucketDeep 获取最大深度之后，平均情况下可以将内存降到原来的 1/8，当数据量大时，两者用时基本差不多
     * <p>
     * 使用最大深度：
     * 使用基数排序，排 80000 个数据，用时 50 ~ 70 ms
     * <p>
     * 不使用最大深度：
     * 使用基数排序，排 80000 个数据，用时 10 ~ 30 ms
     *
     * @param arr
     */
    public static void radixSort(int[] arr) {
        //考虑到基数排序每一次=个桶都需要占用太大的内存空间，所以可以优化bucket的深度
        String deepAndCount = getBucketDeep(arr);
        System.out.println("deepAndCount = " + deepAndCount);
        int deep = Integer.parseInt(deepAndCount.split(":")[0]);
        int maxCount = Integer.parseInt(deepAndCount.split(":")[1]);

        //定义一个桶，用于存放每一个排序后的数据
        //使用最大深度
//        int[][] bucket = new int[10][deep];
        //不使用最大深度
        int[][] bucket = new int[10][arr.length];
        //用于存放每一个桶中存放了多少个数据
        int[] bucketEleNum = new int[10];
        // count 表示去什么位的数字
        int count = 1;
        int num = 1;
        while (count <= maxCount) {
            //现将数据放入到桶中
            int digit;
            //todo 当循环到最后一轮时，会将数组溢出
            for (int i = 0; i < arr.length; i++) {
                digit = arr[i] / count % 10;
                //将个位数据放入到桶中
                bucket[digit][bucketEleNum[digit]] = arr[i];
                //将对应的桶中的数据 +1
                bucketEleNum[digit]++;
            }

            //将count乘以10，第二次就取十位数
            count = count * 10;
            //重新将桶中的数据放入到数组中
            int index = 0;
            for (int j = 0; j < bucketEleNum.length; j++) {
                //这里的 if 判断可以省略，为了方便理解就留下了
                if (bucketEleNum[j] > 0) {
                    //循环遍历第 j 个桶中的数据，将其放入到 arr 中
                    for (int k = 0; k < bucketEleNum[j]; k++) {
                        arr[index] = bucket[j][k];
                        index++;
                    }
                }
                //没放了一个桶中的数据之后，就将桶中的数据设置为 0
                bucketEleNum[j] = 0;
            }
//            System.out.println("第 " + num++ + " 次排序后，arr = " + Arrays.toString(arr));
        }


        //********以下代码是为了分析技术排序的过程*******************************************88

/*        //1、第一轮
        //现将数据放入到桶中
        for (int i = 0; i < arr.length; i++) {
            int digit = arr[i] % 10;
            //将个位数据放入到桶中
            bucket[digit][bucketEleNum[digit]] = arr[i];
            //将对应的桶中的数据 +1
            bucketEleNum[digit]++;
        }
        //重新将桶中的数据放入到数组中
        int index = 0;
        for (int j = 0; j < bucketEleNum.length; j++) {
            //这里的 if 判断可以省略，为了方便理解就留下了
            if(bucketEleNum[j] > 0){
                //循环遍历第 j 个桶中的数据，将其放入到 arr 中
                for (int k = 0; k < bucketEleNum[j]; k++) {
                    arr[index] = bucket[j][k];
                    index ++;
                }
            }
            //没放了一个桶中的数据之后，就将桶中的数据设置为 0
            bucketEleNum[j] = 0;
        }

        //第 1 次排序后，arr = [542, 53, 3, 14, 214, 748]
        System.out.println("第 1 次排序后，arr = " + Arrays.toString(arr));


        //2、第2轮
        //现将数据放入到桶中
        for (int i = 0; i < arr.length; i++) {
            int digit = arr[i] / 10 % 10;
            //将个位数据放入到桶中
            bucket[digit][bucketEleNum[digit]] = arr[i];
            //将对应的桶中的数据 +1
            bucketEleNum[digit]++;
        }
        //重新将桶中的数据放入到数组中
        index = 0;
        for (int j = 0; j < bucketEleNum.length; j++) {
            //这里的 if 判断可以省略，为了方便理解就留下了
            if(bucketEleNum[j] > 0){
                //循环遍历第 j 个桶中的数据，将其放入到 arr 中
                for (int k = 0; k < bucketEleNum[j]; k++) {
                    arr[index] = bucket[j][k];
                    index ++;
                }
            }
            //没放了一个桶中的数据之后，就将桶中的数据设置为 0
            bucketEleNum[j] = 0;
        }

        //第 2 次排序后，arr = [3, 14, 214, 542, 748, 53]
        System.out.println("第 2 次排序后，arr = " + Arrays.toString(arr));

        //3、第3轮
        //现将数据放入到桶中
        for (int i = 0; i < arr.length; i++) {
            int digit = arr[i] / 100 % 10;
            //将个位数据放入到桶中
            bucket[digit][bucketEleNum[digit]] = arr[i];
            //将对应的桶中的数据 +1
            bucketEleNum[digit]++;
        }
        //重新将桶中的数据放入到数组中
        index = 0;
        for (int j = 0; j < bucketEleNum.length; j++) {
            //这里的 if 判断可以省略，为了方便理解就留下了
            if(bucketEleNum[j] > 0){
                //循环遍历第 j 个桶中的数据，将其放入到 arr 中
                for (int k = 0; k < bucketEleNum[j]; k++) {
                    arr[index] = bucket[j][k];
                    index ++;
                }
            }
            //没放了一个桶中的数据之后，就将桶中的数据设置为 0
            bucketEleNum[j] = 0;
        }
        //第 3 次排序后，arr = [3, 14, 53, 214, 542, 748]
        System.out.println("第 3 次排序后，arr = " + Arrays.toString(arr));*/

    }

    /**
     * 获取每一个桶的深度，即 int[][] bucket = new int[10][deep];
     * 思路：
     * 依次遍历每一位数字的个位，当数字相同时对应的数字的个数 + 1，最后取个位数中重复数字最多的个数
     * 然后循环遍历十位，百位，。。。，直到结束
     *
     * @param arr
     * @return
     */
    public static String getBucketDeep(int[] arr) {
        int deep = 0;
        int[] bucketEle = new int[10];
        int digit;
        int countNum;
        int count = 1;
        while (true) {
            countNum = 0;
            for (int i = 0; i < arr.length; i++) {
                digit = arr[i] / count % 10;
                //将对应的桶中的数据 +1
                bucketEle[digit]++;
                //只要当存在这个位数的值不为 0 时，就将 countNum 设为不是0，方便及时退出循环
                countNum = Math.max(countNum, digit);
            }
            if (countNum == 0) {
                break;
            }
            count = count * 10;
            // 当 digit 全部为 0 时可以 退出循环了
            int max = Arrays.stream(bucketEle).max().getAsInt();
            deep = Math.max(max, deep);
            //将 bucketEle 中的数据全部变为0
            for (int i = 0; i < bucketEle.length; i++) {
                bucketEle[i] = 0;
            }

        }
        return deep + ":" + count / 10;
    }
}
